package org.algorithm.wE1.数组.三月.第四周;

import java.util.Arrays;

/**
 * @author zhx
 * @date 2022-03-21 星期一18:25
 *
 * url: https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class 接雨水 {


    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }

    public static int trap(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }
        int ans = 0;
        int size = height.length;
        int[] leftMax = new int[size];
        int[] rightMax = new int[size];
        for (int i = 1; i < size; i++) {
            leftMax[i] = Math.max(height[i],leftMax[i-1]);
        }
        for (int i = size-2; i >=0 ; i--) {
            rightMax[i] = Math.max(height[i],rightMax[i+i]);
        }
        for (int i = 0; i <size ; i++) {
            ans += Math.min(leftMax[i],rightMax[i])-height[i];
        }
        return ans;
    }


}
